package problem;

import javafx.util.Pair;

import javax.print.DocFlavor;
import java.util.*;

public class S_127 {
    //单词接龙
    /*给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。
    转换需遵循如下规则：
        每次转换只能改变一个字母。
        转换过程中的中间单词必须是字典中的单词。
*/
    //1.BFS
    class Solution {
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            int len=beginWord.length();
            //键是通用状态，值是该通用状态下所有值的单词集合
            HashMap<String,ArrayList<String>> allComboDict=new HashMap<>();
            //遍历wordList
            wordList.forEach(
                    word->{     //word是每个单词
                        for(int i=0;i<len;i++){ //遍历出wordList中的每个单词的每个通用状态,因为通用状态可能重复
                            String newWord=word.substring(0,i)+"*"+word.substring(i+1,len);
                            ArrayList<String> list=allComboDict.getOrDefault(newWord,new ArrayList<>());
                            list.add(word);
                            allComboDict.put(newWord,list);
                        }
                    }
            );
            Queue<Pair<String,Integer>> queue=new LinkedList<>();
            queue.add(new Pair<>(beginWord,1)); //添加起点
            HashMap<String,Boolean> visited=new HashMap<>();
            visited.put(beginWord,true);

            while(!queue.isEmpty()){
                Pair<String, Integer> node = queue.remove();    //取出头节点
                String word=node.getKey();                      //当前节点的单词
                int level=node.getValue();                      //当前节点的步数
                for(int i=0;i<len;i++){
                    //遍历出该单词的所有状态,newWord代表一个状态
                    String newWord=word.substring(0,i)+"*"+word.substring(i+1,len);
                    for(String w:allComboDict.getOrDefault(newWord,new ArrayList<>())){
                        if(w.equals(endWord)){
                            return level+1;
                        }
                        if(!visited.containsKey(w)){            //该单词有邻接单词
                            visited.put(w,true);
                            queue.add(new Pair<>(w,level+1));
                        }
                    }
                }
            }
            return 0;
        }
    }
}
